package com.dmall.chapter03.section04;

import java.util.HashSet;
import java.util.Set;

/**
 * 定义一个容器将访问的节点都放入到容器中
 * 时间复杂度：O(n)
 * 空间复杂度：O(n)
 * @author xiao1.wang
 * @date 2020-12-02 12:12:28
 */
public class Leetcode141V1 {

    public boolean hasCycle(ListNode head) {

        Set<ListNode> visited = new HashSet<>();

        while (head != null) {
            if (visited.contains(head)) {
                return true;
            }
            visited.add(head);
            head = head.next;
        }
        return false;
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
